package main;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class TreeTraverse {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right1 = new TreeNode(3);
        TreeNode left2 = new TreeNode(4);
        TreeNode right2 = new TreeNode(5);
        TreeNode left3 = new TreeNode(6);
        TreeNode right3 = new TreeNode(7);
        root.left = left1;
        root.right = right1;
        left1.left = left2;
        left1.right = right2;
        right1.left = left3;
        right1.right = right3;
        System.out.println(new TreeTraverse().inorderTraversal(root));;
    }

    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> nodes = new LinkedList<>();
        dfs(root,nodes);
        return nodes;
    }

    private void dfs(TreeNode root,List<Integer> nodes){
        if (root != null){
            dfs(root.left,nodes);
            nodes.add(root.val);
            dfs(root.right,nodes);
        }
    }

    public List<Integer> inorderTraverse(TreeNode root){
        List<Integer> nodes = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        return nodes;
    }

}
